package DP1;

/**
 * 1262. 可被三整除的最大和
 * 给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
 * 输入：nums = [3,6,5,1,8]
 * 输出：18
 * 解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
 */
public class Main14 {
    public static void main(String[] args) {
        int[] nums = {3,6,5,1,8};
        System.out.println(maxSumDivThree(nums));
    }

    public static int maxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        for (int i = 0; i < nums.length; i++) {
            int mod = nums[i] % 3;
            int a = dp[(3 + 0 -mod) % 3];
            int b = dp[(3 + 1 -mod) % 3];
            int c = dp[(3 + 2 -mod) % 3];
            if (a!=0 || mod == 0) dp[0] = Math.max(dp[0], a + nums[i]);  // 0 --- > 0
            if (b!=0 || mod == 1) dp[1] = Math.max(dp[1], b + nums[i]);  // 1 --- >
            if (c!=0 || mod == 2) dp[2] = Math.max(dp[2], c + nums[i]);  // 2 --- >
        }
        return dp[0];
    }
}
